package basic._01_快速排序;

import java.util.Arrays;

/**
 * @author： YHSimon
 * @date： 2022-07-06 22:57
 */
public class Solution {
    public int partition(int[] nums, int low, int high) {
        // 将当前表中第一个元素设为枢轴值，对表进行划分
        int pivot = nums[low];
        while (low < high) {
            while (low < high && nums[high] >= pivot) high--;
            nums[low] = nums[high]; // 将比枢轴值小的元素移动到左侧
            while (low < high && nums[low] <= pivot) low++;
            nums[high] = nums[low]; // 将比枢轴值大的元素移动到右侧
        }
        nums[low] = pivot;  // 数轴元素存放到最终位置
        return low;       // 返回存放枢轴的最终位置
    }

    public void quickSort(int[] nums, int low, int high) {
        if (low < high) {
            int pivotPos = partition(nums, low, high);//划分
            quickSort(nums, 0, pivotPos - 1);
            quickSort(nums, pivotPos + 1, high);
        }
    }

    public void quickSort(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {4, 5, 1, 3, 9, 5, 4};
        s.quickSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}
